import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created by zhourh on 2018/6/11.
 *
 * 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
 *
 * 递归
 */
public class AverageOfLevelsInBinaryTree {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        System.out.println(new AverageOfLevelsInBinaryTree().averageOfLevels(root));
    }

    /**
     * 深度优先遍历
     * @param root
     * @return
     */
    public List<Double> averageOfLevels(TreeNode root) {
        List<List<Integer>> treeList = new ArrayList();
        convertLists(root, treeList, 0);
        List<Double> result = new ArrayList();
        for (int i = 0; i < treeList.size(); i++ ) {
            result.add(i, averageOfList(treeList.get(i)));
        }

        return result;
    }

    public void convertLists(TreeNode treeNode, List<List<Integer>> treeList, int level) {
        if (treeList.size() - 1 < level) {
            List<Integer> levelList = new ArrayList();
            treeList.add(level, levelList);
        }

        treeList.get(level).add(treeNode.val);

        if (treeNode.left != null) {
            convertLists(treeNode.left, treeList, level + 1);
        }

        if (treeNode.right != null) {
            convertLists(treeNode.right, treeList, level + 1);
        }
    }


    private double averageOfList(List<Integer> list) {
        if (list == null || list.isEmpty()) {
            return 0;
        }

        long sum = 0;
        for (Integer integer : list) {
            sum += integer;
        }

        return sum * 1.0 / list.size();
    }

}
